class Solution:
    """
    方法： 使用动态规划判断字符串s3是否可以由s1和s2交错组成
           dp[j]表示s1的前i个字符和s2的前j个字符是否可以交错组成s3的前i+j个字符
           当前字符可以来自s1或s2:
           - 来自s1: dp[j] = dp[j] && s1[i-1] == s3[i+j-1] 
           - 来自s2: dp[j] = dp[j-1] && s2[j-1] == s3[i+j-1]
    
    Args:
        s1: str - 第一个输入字符串
        s2: str - 第二个输入字符串
        s3: str - 目标字符串
    
    Returns:
        bool: s3是否可以由s1和s2交错组成
    
    Time: O(m*n) - m和n分别为s1和s2的长度，需要填充m*n的dp表
    
    Space: O(n) - 使用一维数组优化空间，n为s2的长度
    """
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        
        # 使用一维数组优化空间复杂度
        dp = [False] * (n + 1)
        dp[0] = True  # 空字符串可以由两个空字符串交错组成
        
        # 初始化第一行（仅使用s2的情况）
        for j in range(1, n + 1):
            dp[j] = dp[j-1] and (s2[j-1] == s3[j-1])
        
        for i in range(1, m + 1):
            # 初始化当前行第一个元素（仅使用s1的情况）
            dp[0] = dp[0] and (s1[i-1] == s3[i-1])
            
            for j in range(1, n + 1):
                # 当前字符可以来自s1或s2
                from_s1 = dp[j] and (s1[i-1] == s3[i+j-1])
                from_s2 = dp[j-1] and (s2[j-1] == s3[i+j-1])
                dp[j] = from_s1 or from_s2
        
        return dp[n]